package leetcode.graph;

import java.util.LinkedList;
import java.util.Queue;

public class IsGraphBipartite785 {
    class Solution1 {
        public boolean isBipartite(int[][] graph) {
            int n = graph.length;
            if (n == 0) {
                return true;
            }
            Queue<Integer> queue = new LinkedList<>();
            int[] color = new int[n];
            for (int i = 0; i < n; i++) {
                if (color[i] == 0) {
                    queue.add(i);
                    color[i] = 1;
                }
                while (!queue.isEmpty()) {
                    int curNode = queue.poll();
                    for (int j : graph[curNode]) {
                        if (color[j] == 0) {
                            color[j] = color[curNode] == 1 ? 2 : 1;
                            queue.add(j);
                        } else if (color[j] == color[curNode]) {
                            return false;
                        }
                    }
                }
            }
            return true;
        }
    }

    class Solution2 {
        public boolean isBipartite(int[][] graph) {
            if (graph == null || graph.length == 0 || graph[0] == null || graph[0].length == 0) {
                return true;
            }
            int n = graph.length;
            int[] color = new int[n];
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                if (color[i] == 0) {
                    queue.add(i);
                    color[i] = 1;
                }
                while (!queue.isEmpty()) {
                    int curNode = queue.poll();
                    for (int j : graph[curNode]) {
                        if (color[j] == 0) {
                            color[j] = color[curNode] == 1 ? 2 : 1;
                        } else if (color[j] == color[curNode]) {
                            return false;
                        }
                    }
                }
            }
            return true;
        }
    }
}
